/**
 * @a https://leetcode.cn/problems/valid-parentheses/
 */

#include "../common.h"

class Solution {
public:
    bool isValid(string s) {
        vector<char> st;
        for(auto ch : s){
            if(ch == '(' || ch == '[' || ch == '{') st.push_back(ch);
            else{
                if(st.empty()) return false;

                char tmp = st.back();
                if((ch == ')' && tmp == '(') || (ch == ']' && tmp == '[') || (ch == '}' && tmp == '{')) st.pop_back();
                else return false;
            }
        }
        return st.empty();
    }
};